/*public class Solution {
    // 求完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 计算树的高度
        int leftHeight = getHeight(root, true); // 获取左子树的高度
        int rightHeight = getHeight(root, false); // 获取右子树的高度

        // 如果左子树的高度等于右子树的高度，则说明左子树是满二叉树
        if (leftHeight == rightHeight) {
            // 计算节点数量为 2^leftHeight - 1 + 当前节点 + 右子树节点数量
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            // 否则递归计算左子树节点数量 + 当前节点 + 右子树节点数量
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    // 获取树的高度
    private int getHeight(TreeNode node, boolean left) {
        int height = 0;
        while (node != null) {
            height++;
            node = left ? node.left : node.right; // 根据参数决定向左还是向右
        }
        return height;
    }

    // TreeNode定义
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
*/
//方法二
// TreeNode 类单独定义
/*
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // 求完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 计算树的高度
        int leftHeight = getHeight(root, true); // 获取左子树的高度
        int rightHeight = getHeight(root, false); // 获取右子树的高度

        // 如果左子树的高度等于右子树的高度，则说明左子树是满二叉树
        if (leftHeight == rightHeight) {
            // 计算节点数量为 2^leftHeight - 1 + 当前节点 + 右子树节点数量
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            // 否则递归计算左子树节点数量 + 当前节点 + 右子树节点数量
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    // 获取树的高度
    private int getHeight(TreeNode node, boolean left) {
        int height = 0;
        while (node != null) {
            height++;
            node = left ? node.left : node.right; // 根据参数决定向左还是向右
        }
        return height;
    }

    // 这里是你可以测试的 main 方法
    public static void main(String[] args) {
        // 测试代码
        Solution solution = new Solution();

        // 创建树节点
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        // 测试 countNodes 方法
        int result = solution.countNodes(root);
        System.out.println("节点个数: " + result); // 输出应为 6
    }
}
*/
// TreeNode 类单独定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // 求完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 计算树的高度
        int leftHeight = getHeight(root, true); // 获取左子树的高度
        int rightHeight = getHeight(root, false); // 获取右子树的高度

        // 如果左子树的高度等于右子树的高度，则说明左子树是满二叉树
        if (leftHeight == rightHeight) {
            // 计算节点数量为 2^leftHeight - 1 + 当前节点 + 右子树节点数量
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            // 否则递归计算左子树节点数量 + 当前节点 + 右子树节点数量
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    // 获取树的高度
    private int getHeight(TreeNode node, boolean left) {
        int height = 0;
        while (node != null) {
            height++;
            node = left ? node.left : node.right; // 根据参数决定向左还是向右
        }
        return height;
    }

    // 这里是你可以测试的 main 方法
    public static void main(String[] args) {
        // 测试代码
        Solution solution = new Solution();

        // 创建树节点
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        // 测试 countNodes 方法
        int result = solution.countNodes(root);
        System.out.println("节点个数: " + result); // 输出应为 6
    }
}
